Teoría de Grafos

Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

Complementos del Grafo

Aristas Adyacentes:

Dos aristas son adyacentes si tienen un vértice común.

Lazos:

Es una arista cuyos extremos indicen sobre el mismo vértice.

Aristas Paralelas:

Dos o más aristas que son incidentes (que se conectan) al menos con dos vértices iguales.

Vértices Adyacentes:

Los vértices son adyacentes cuendo comparte la misma arista.

Grado de un Vértice

Se puede definir como la cantidad de aristas que parten desde o hacia un mismo vértice

Un grafo dirigido u orientado, es un tipo de grafo en el cual el conjunto de las aristas tiene una dirección definida, a diferencia del grafo generalizado, en el cual la dirección puede estar especificada o no.

Grafo simple o simplemente grafo es aquel que acepta una sola una arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Es la definición estándar de un grafo. No contiene aristas paralelas, lazos ni aristas dirigidos.

Un grafo ​conexo o conectado es un grafo en que todos sus vértices están conectados por un camino ​ o por un semicamino. Un grafo que no es conexo se denomina grafo disconexo o inconexo.
Los subgrafos conexos máximos de un grafo no dirigido se llaman componentes o componentes conexos.​

Un subgrafo es un grafo que esta contenido dentro de otro grafo y que se obtiene eliminando algunas aristas y vértices del grafo principal

Es aquella que muestra de la forma más rústica cómo está compuesto un grafo, esto es que donde se coloque un 1 se representa como una arista que una a los dos nodos y con 0 donde no hay ninguna unión; así, se puede obtener un grafo a partir de la matriz de adyacencia.

Por ejemplo:

Si tenemos los vértices a, b, c, d, e y las aristas ab, bc, be, ed, de, ad

Ruta o Camino de Euler

Es una trayectoria que contiene todas las aristas del grafo y recorre una arista exactamente una vez.

Condiciones:

El Grafo debe de ser conexo.
Exactamente 2 vértices son de grado impar, todos los demás deben de ser de grado par.
Se comienza en uno de los vértices de grado impar y se termina en el otro vértice impar.

Circuito o ciclo de Euler

Es un Camino de Euler con la diferencia que empieza y termina en el mismo vértice es decir es un camino cerrado que recorre cada arista exactamente una vez.

Condiciones:

El grafo es conexo
Todos los vértices son de grado par
Se comienza y se termina en el mismo vertice

Ruta o Camino de Hamilton

Es un camino (es decir, una sucesión de aristas adyacentes), que visita todos los vértices del grafo una sola vez.

Circuito o Ciclo de Hamilton

A diferencia de un Camino de Hamilton, en un ciclo, el primer y último vértice visitado coinciden.

Coloración de Grafos

Es un caso especial de etiquetado de grafos; es una asignación de etiquetas llamadas colores a elementos del grafo.
De manera simple, una coloración de los vértices de un grafo tal que ningún vértice adyacente comparta el mismo color es llamado vértice coloración.
El método de coloración, consiste en determinar el grado de cada vértice y en un orden de mayor a menor, establecer etiqueta de color cuidando que ningún vértice adyacente comparta color; finalmente el grado cromático de un grafo, será determinado por el número de colores utilizados en su coloración.

1. Teniendo en cuenta los vértices 1, 2, 3, 4 y las aristas 12, 23, 34, 41, graficar su grafo respectivo, así como su matriz de adyacencia.

2. Teniendo en cuenta los vértices a, b, c, d y las aristas ab, bc, cd, da, elaborar el grafo y la matriz de adyacencia respectivas.

4. Calcular la Ruta o Ciclo de Euler y la Ruta o Ciclo de Hamilton del siguiente grafo:

5. Calcular el grado cromático de: